COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	***Goes after Iteration***
C00005 00003	Example:    FOR I: = 1 TO 4 DO WRITE(I * I)
C00006 00004	Because of the similarity of the rectangles to contour lines on a map, this
C00007 00005	The Best is the Enemy of the Good
C00012 00006	Arrays
C00017 00007	Programming Cliches
C00021 00008	Discrete Simulation
C00029 00009	Final Project: Bidge Bidding (Fall 1983)
C00033 00010	Monte Carlo Methods
C00039 00011	It is not ordinarily  possible to generate truly random numbers on a
C00044 ENDMK
C⊗;
***Goes after Iteration***

-Human Execution of Computer Programs-

A computer program can be executed by a human.  There are many good
reasons for executing a program "by hand", including:
	(1) A program may be desk-checked on a small problem to which the
	    answer is known.   Unexpected intermediate results show likely 
	    locations for errors.

	(2) A program written by another person can be hand executed to get
	    insight into the logic of its design.

To hand-execute an iteration of the form FOR I:= A TO B DO S:
	(1) Evaluate A and B getting numerical values N↓A and N↓B

	(2) Write down FOR I:= N↓A TO N↓B DO

	(3) Draw a vertical rectangle, leaving it open at the bottom until
	    you know how much room the execution will take.

	(4) Inside the rectangle, write I = N↓A

	(5) If I <= N↓B, hand-execute command S; otherwise go to step 7.
	    If S is itself an iteration its execution record will be a
	    second rectangle inside the first one.

	(6) Write I = (one greater than the previous value) and return to
	    step 5. 

	(7) Close off the bottom of the rectangle, and write "I = ?", to
	    show that after completion of an iteration, the iteration variable 
	    is left with an unspecified value.

Example:    FOR I: = 1 TO 4 DO WRITE(I * I)

	FOR I: = 1 TO 4 DO
	I = 1
	WRITE(I * I)		1
	I = 2
	WRITE(I * I)		4
	I = 3
	WRITE(I * I)		9
	I = 4
	WRITE(I * I)		16
	I = 5

	I = ?

Example:    FOR I: = 1 TO 3 DO
		FOR J: = I + 1 TO 3 DO
			WRITE(I * J)

	FOR I: = 1 TO 3 DO
	I = 1
	FOR J: = 2 TO 3 DO
		J = 2
		WRITE(I * J)		2
		J = 3
		WRITE(I * J)		3
		J = 4
		J = ?

	I = 2
	FOR J: = 3 TO 3 DO
		J = 3
		WRITE(I * J)		6
		J = 4
		
		J = ?

	I = 3
	FOR J: = 4 TO 3 DO
		J = 4
		(no other action)
		
		J = ?
	I = 4
I = ?

Because of the similarity of the rectangles to contour lines on a map, this
method is called the -contour model- of program execution.  As we go deeper
into Pascal, we will find other features of the language that introduce
contour lines, each with its own rules for filling in the boxes.

The Best is the Enemy of the Good

A frequent task in computing is to find the best, for some purpose, of a
finite set.  If  f(i) is my predicted profit from making i widgets this
year, and my factory can't make more than 1000 of them in a year, I need to
know the value of i between 1 and 1000 that makes f(i) the largest.  I may
also have more than a passing interest in the value f(i) has for that value
of i.

The naive way to do the problem is to test each value of i in turn, against
all the other numbers, printing i if it wins all these contests.  In
outline, here is the program:

	FOR I:=1 TO 1000 DO
		BEGIN
		LOSSES:=0;
		FOR J:=1 TO 1000 DO
			IF F(I) < F(J) THEN
				LOSSES:=LOSSES + 1;
		IF LOSSES=0 THEN
			WRITELN(I, F(I))
		END

This program has several problems.  It potentially prints several equally
good values of i, though that isn't necessarily bad.  It takes far too much
time, executing some operations a million times when it could be
redesigned not to do anything more than a thousand times.  The faster
program is also shorter.

The problem with the program above is that it is conducting a contest among
the numbers from 1 to 1000 as if it were a round robin tournament, where
everyone plays a game against everyone else.  To find the best player using
the fewest games, it is far more efficient to use a knockout tournament,
where losers are eliminated from further play.  A program can run through
the numbers from 1 to 1000, keeping track only of the current number, and of
that previous number that beat all the others.  Using a variable BESTSOFAR
to keep the current winner, the program is:

	BEGIN
	BESTSOFAR:=1;
		FOR I:=2 TO 1000 DO
			IF F(I) > F(BESTSOFAR) THEN
				BESTSOFAR:=1;
	WRITELN(BESTSOFAR, F(BESTSOFAR))
	END.

A slight improvement in efficiency can be made by not discarding the best
value of f so far:

	BEGIN
	BESTSOFAR:=1;
	FBEST:=F(1);
	FOR I:=2 TO 1000 DO
		BEGIN
		FI:=F(I);
		IF FI > FBEST THEN
			BEGIN
			FBEST:=FI;
			BESTSOFAR:=I;
			END
		END
	END


The same pattern can, of course, be used to find the smallest, by changing
">" to "<".  We can find the first or last number that meets a condition by
similar programs.  Say we want to find the largest number between 1 and
1000 that meets a certain test.  Here are several methods:

(1)	LARGEST:=0;
	FOR I:=1 TO 1000 DO
		IF TEST(I) THEN
			LARGEST:=I;
	IF I > 0 THEN WRITELN(`LARGEST:' I)
	ELSE WRITELN(`NO NUMBER SATISFIES THE TEST')

(2)	I:=1000;
	WHILE (I > 0) AND NOT TEST(I) DO
		I:=I-1;
	IF I > O, etc.

(3)	FOR I:=1000 DOWNTO 1 DO
		IF TEST(I) THEN
		BEGIN LARGEST:=I
		GO TO 99;
		END
	WRITELN(`NO NUMBER SATISFIES THE TEST');
	GO TO 100;
	99: WRITELN(`LARGEST:' LARGEST)
	100: END.

Arrays

Pascal, with almost every programming language, contains builtin functions the
programmer can not change, like the square root and trigonometric
functions.  The world also contains functions that change with time, like
COHORT(A) = the number of people of age A, or INCOMETAX(I), the income tax
on I dollars.  Such functions are represented in programming languages by
arrays: tables which store the value of the function for each argument in a
certain range.  The allowed operations include not only finding the value
of the function on any argument within range (a _value access_ to the
array) but also specifying a new value of the function on any argument
within range( a _reference access_ to the array)

For example, a program to read 150 numerical data from a file and print
them numbered in three columns, can begin by reading each datum and letting
it be the value of the array for one argument.  After all have been read
and stored, the program finds the values stored in the array, in the
correct order for printing.  The program, in outline, is this:

	(Declarations)
	BEGIN
	FOR I:=1 TO 150 DO
		READ(A[I]);
	FOR J:=1 TO 50 DO
		WRITELN(J, A[J],J+50,A[J+50],J+100,A[J+100])
	END.

If A is an array with index type T↓1 and value type T↓2, and I is an
expression of type T↓1, we can use A[I] to mean the value of A for the
argument I.  This program fragment:

	S:=0;
	FOR J:=0 TO 2 DO
		S:=S+A[J+1];
	WRITE(S)

prints the value of A[1] + A[2] + A[3].  If A[I] appears in an assignment
context, a new value is given to A for the argument I; after executing this
program fragment:

	FOR I:=1 TO 3 DO
		IF I=2 THEN A[I]:=3.0
		ELSE READ(A[I])

with the input file  5.7 6.9
we will have A[1] = 5.7, A[2] = 3.0, A[3] = 6.9

In Pascal, an array type is of the form
	
	ARRAY[T↓1] OF T↓2

where T↓1 is the argument type, and T↓2 the result type.  The argument type
must be a subrange.  The result type can be any type for which assignment
is possible, ie. any non-file type.  An array is declared in the same way a
program variable is, using an array type.  The declaration

	VARIABLE A: ARRAY[1..10] OF REAL

declares A as an array with integer indices in (1,10), with real number
values.  

An array could be declared

	VARIABLE CODE: ARRAY[`A'..`Z'] OF CHAR

Such an array could be used to store a function from letters to letters for
decoding a substitution cipher.

Arrays may have more than one argument.  An array to hold a tax table for
specified income (in $1000s) and family size would be declared:

	VARIABLE TAXTBL: ARRAY[1..2000, 0..20] OF INTEGER

or giving the array type a name of its own,

	...
	...
	TYPE TXTBTY = ARRAY[1..2000, 0.20] OF INTEGER;
	...
	...
	VARIABLE TXTBL:TXTBTY
	...
	...

An exercise in the use of arrays.

Write a program which reads the degree (≤20) of a polynomial, then the coefficients
starting with the constant term.  The program should print the polynomial, its
square, and its cube.  Try it on the polynomial

	16 - 32x + 24x↑2 - 8x↑3 + x↑4 .

Programming Cliches

In ordinary language, there are phrases or sentences we use over and over
again, like "Do you swear to tell the truth, the whole truth and nothing
but the truth?", or "Ham on rye, hold the mustard."  We know that they
serve their function precisely, and we save effort by not having to
reinvent them constantly.  Such cliches are found in computer programs too.
This book presents a number of them; they are worth memorizing.  Here is
one to exchange the contents of two variables.

To exchange the places of two cars in parking spaces, we must have a third
place to put a car.  If car A is in space X and car B is in space Y, we
move A from space X to a third space T, B from space Y to space X, and A
from space T to space Y.  In programs, we don't give numbers names that
follow them around, like "car A" above; we name them by saying where they
are.  The program fragment, analogous to the car swap, that exchanges the
numbers in variables X and Y is

	T:=X;
	X:=Y;
	Y:=T

where X,Y, and T are variables of the same type, and T is what we call a
temporary variable; that is, the value put into it is used at once and
never again.

Another cliche is used to find the value of i for which f(i) is a maximum
(A<=i<=B); 
	MAX:=F(A);	(*SMALLEST POSSIBLE VALUE*)
	LOCMAX:=A;
	FOR I:=A+1 TO B DO
		IF F(I) > MAX THEN
			BEGIN
			MAX:=F(I);
			LOCMAX:=I
			END;

This cliche embodies the insight that finding the largest of a finite set
does not require that every element be compared to every other.

Priority Cliches

If a program must choose between several courses of action, often there is
a priority order; if the conditions for several actions are all true, the
program must perform the action of highest priority.

Example:

IF heart attack THEN administer CPR
ELSE IF house on fire THEN call 911
ELSE IF hungry THEN go for food
ELSE IF unprepared THEN study.

Discrete Simulation

Assume we have the schedule fo all daily airline flights among a group of
cities.  We are planning a guide for air travelers which shows, for each
origin and destinations city, not only the direct flights, but connections
that reach the destination by one or more changes of planes.   We will
include a connection if it is the fastest way to go for someone arriving at
the airport just in time to emplane on it.  To simplify matters, we assume
all flights are daily, and that changes of plane can be carried out
instantly; in the real world, the problem is much more complex.

Before trying to program the problem, let's look at an algorithm for it.
We will simulate a time period in which a group of travelers starts out on
every flight.  When the group on one flight reaches a city, we check if
any other travelers from the same original point of departure started later
and reached their current city earlier; if so, we make no further use of
this group.  If, however, the group has used good connections so far, as
shown by not having been outraced to the current city, we record this
itinerary in the list of connections.  We also split them up, and let some
of them continue on each flight out of their current city.  We continue this
process for at least twenty-four hours; in fact, as long as there are still
travelers who started during the original twenty-four hours, we must keep
the entire process going to check for alternative routes.

When we simulate the events of this scenario, which are arrivals and
departures at airports, we have to do it in chronological order.
Otherwise, when we find traveler A arriving at city B from city C, we may
not yet know that traveler D, by a different route, can leave city C
earlier and reach city B sooner.  To make things happen in chronological
order, we will keep a master list of all future events that are certain to
happen, sorted (i.e., arranged in increasing order) by the time at which
the event will happen.  When we make an event happen, it will always be the
first on the master list.  As we simulate an event, we put on the master
list all future events it implies.  This technique is the general method
for what are called ←discrete simulation← problems, whether they concern
air or road traffic, serving customers in a bank, or .... .

In our particular problem, we start off by putting all scheduled departures
on the master list, and then "start the clock running".  The first event
drawn from the master list is the first flight departure of the day.  We
put on it a group of travelers, represented by their city and time of
origin, and insert their predicted arrival at another city into the master
list.   We then go on to the next event from the master list. Notice that
the "clock" of our simulation is not a counter; it only shows those times
at which some actual event happens.

As we continue through the simulated day, we begin to process arrivals.
We need to be able to tell if these arrivals are the completions of good
connections, so we keep track of the starting time of the most recent good
connection between each pair of cities.  When we check travelers in who
began in city A and arrive at city B, if we find that some other travelers
have already arrived from city A who began later, we may ignore the current
arrivals; theirs is not the best connection.  The record keeping is done
with an array of starting times, indexed by the numbers of the origin and
destination city.

As we proceed through the simluation, we eventually begin to process
travelers who have changed planes several times; we need to keep track of
their complete itinerary.  We can do this by building up a list of flights,
each of which shows city and time of origin, and the  cities and times of
one leg of a trip.  If it is not the first leg of the trip, it also shows
the index of the immediately preceding leg of the trip.  Each traveler is
represented, then, by the index of the last leg of his trip; we can trace
back through the earlier legs if needed, e.g. for eventual output of
connections.   We can't stop the simulation until all travelers who began
during the first twenty-four hours are gone.  We can keep count of how many
there are, and stop when the count is zero and the clock is past the first
day.

We can assume that all departure and arrival times are given on a
twenty-four hour clock.


***********
ADD MORE

Final Project: Bidge Bidding (Fall 1983)

A hand of cards, in the game of bridge, is evaluated for ←high card points←
(HCP) on the scale A=4, K=3, Q=2, J=1.  The _distributional value_ is 3 for
each void suit, 2 for each one-card suit, 1 for each 2-card suit, and 1 for
each card beyond the fifth in a suit.  The following hand has 11 HCP and a
distributional value of 4 for a _total valuation_ of 15 points.

	SA SJ S9 S3
	H7
	DQ DJ D10 D8 D5 D2
	CK C9

A hand with distributional value no more than 1 is called balanced.

Opening bids in bridge can be made according to these rules:
Balanced Hands (Use HCP)
	16 to 18 HCP: Bid 1NT
	22 to 24 HCP: Bid 2NT
	25 to 27 HCP: Bid 3NT
	Other ranges: bid as if unbalanced

Unbalanced Hands(Use total evaluation)
	21 points or more: Bid 2C
	6-12 points and an 8 card suit:  Bid 4 of the suit.
	6-12 points and an 7 card suit:  Bid 3 of the suit.
	6-12 points and a 6 card suit, not clubs: Bid 2 of the suit.
	13  points or more, no other bid:  Bid 1 of best suit.
	No other satisfactory bid: "Pass".

The best suit is the longest; if two are equally long, normally bid the higher one
(Spades > Hearts > Diamonds > Clubs).

Fancy Stuff for a better program:

With two non-adjacent best suits, bid the lower one.  Restrict the bid of 3
or 4 of a suit to defenseless hands  (no more than 3 HCP in the other
suits).  Use the 3NT bid to show 5 or more cards in each minor suit
(diamonds, clubs) with total evaluation of 13 or more.  Unbiddable suits
include 4-card majors, all 4-card suits of two HCP or less.

Your program should read a file where each data line looks like this
example:

	D8 CK H7 DQ C9 DT S9 S3 D2 D5 SJ SA DJ. (DT is the 10 of diamonds).

It should print a correct opening bid for each hand.  The last line is the sentinel
`STOP'. 

Test your program on file CS:BRIDGE.TRY  and files of your own design.  The
file  CS:BRIDGE.DAT will be made available for your graded run at 3:30 pm on
the last day of class.  We do this intentionally, to enforce systematic testing.

If you know more about bridge than we do, feel free to program a better bidding
strategy; document the strategy your program follows, in any case.
Monte Carlo Methods

There is no part of a computer that resembles dice, cards, a spinning coin,
or any other such device prized for its randomness.  Still, at times we
want to use a computer to study the behavior of systems that do contain
random elements.  The telephone company tries to ensure that its circuits
will accomodate not only average traffic, but most of the occasional
"random" peaks.  Similar studies can be made of vehicle traffic, customers
queueing (yes, it's an English Word) in a bank, or evolution of bird
species.  Often there seems to be no better way to analyze such partially;
random systems than to simulate them: to write computer programs that
behave as they do, including their random elements.

Just as all polynomials can be built up by addition and multiplication, so
can most random phenomena be built up from a process that picks a random
numbers.  Ordinarily, the random number is picked fro ma certain range, its
possible values in that range are equally spaced, and they are all equally
likely.  A process that does this we call a ←random number generator←.  It
might pick an integer between 0 and MAXINT, or a real number between 0 and
1; either would be useful.  In a computer, a random number generator will
typically be a function or procedure that returns a value according to the
rules above.

Let's assume we have a random number generator procedure RANDOMREAL, which
gives its variable argument a real number value between 0 and 1.  The
chance that the value lies between A and B, if 0<=A<B<1, is roughly B-A.
Using R, we can simulate a dice roll. After the procedure call
RANDOMREAL(X), we can say the number on the dice is 1 if 0<=x<1/6, 2 if
1/6<+X<2/6, etc.  The formula TRUNC(X/6)+1 gives the number on the die; it
is equally likely to have any value from 1 to 6.

A more complicated random system to simulate is an atom of a radioactive
element.  Say it has a 1% chance of decaying in each second, if it has not
already done so.  That is, the chance it decays in the first second is
0.01.  The chance it decays in the second second is 0.01 of the remaining
99/100 of the time, or 0.01 X 0.99.  The chance it decays in the n↑th
second is then 0.99↑n-1 X 0.01.  If our random number generator
RANDOMREAL(X) gives us a real number X between 0 and 1, we can compute a
time t for the atom to decay by setting 
t=1 if 0.99<=X<1;
t=2 if 0.99↑2<=X<=0.99;
t=3 if 0.99↑3<=X<=0.99↑2, etc.

Taking logarithms, we see
t=1 if 1>= logX/log0.99 > 0
t=2 if 2>= logX/log0.99 > 1
t=3 if 3>= logX/log0.99 > 2, etc.

we can use the formula t= truncate(logX/log0.99) + 1

To simulate an event that has probability P of occurring, generate a random
real number X in the range )..1; the event occurs if X<P.  Alternatively,
generate a random integer X in the range 0..MAXINT; the event occurs if
X<P*MAXINT.  

There is no Pascal standard random number generator.  Many Pascal systems
include one and users should ordinarily prefer such a "certified" random
number generator to a home made one.  The typical random number generator
requires a starting value, called a seed, which determines the sequence of
subsequent values.  If the same program is run a second time with the same
seed, the same results will be found, so to carry out statistically
independent executions, each time the program is run, a new seed should be
used.  The seed should be recorded, so that if bugs are found or suspected
the program can be run again under identical conditions.

A typical programming cliche for using a seeded random number generator is:

	READ(SEED);
	WRITELN("SEED=", SEED);
	X:=SEED;
	WHILE ... DO
		BEGIN
		RANDOM(X);
		Process random number X
		END

It is not ordinarily  possible to generate truly random numbers on a
correctly operating computer; we satisfy ourselves by generating sequences
that meet most statistical tests for randomness, like the requirement that
in a large trial, nearly equal fractions of the random numbers fall in each
percent of the possible range.  The typical method, using an integer X is

	X:= (X * K1)MOD K2
where K1 and K2 are carefully selected constants.  A builtin random number
generator usually uses double precision integer arithmetic, so it can not
easily be programmed in standard Pascal.  To demonstrate the pattern of
behavior, here is the sequence of random numbers if K1 = 23, K2 = 100, and
the see is 47:

81 63 49 27 21 83 09 07 61 03

69 87 01 23 29 67 41 43 89 47

81 63 etc.

Among the flaws of this choice, the sequence repeats after generating only
twenty numbers, and it generates only numbers that end in 1,3,7, or 9.  If
the seed had been 25, the sequence would have been 25 75 25 75 25, etc.  By
choosing K1=    , K2=    , however, we could guarantee that every number
between 1 and     would be generated  once before repeating, for any seed
in that range.

If you must build your own random number generator, see Knuth, Vol.2, pg  ,
for some rules of thumb which ensure good performance.

Here is a Pascal program using an integer random number procedure to
simulate a dice game.  Player 1 rolls a die once, then player 2 rolls it
twice, player 1 rolls it three times, etc., until someone rolls a 6.  The
program simulates the game a number of times to estimate the probability
that A wins the game.

     CONSTANT C=MAXINT/6
     READ(SEED, NUMTRIALS)
     X:=SEED;
     WINS:=0;
     FOR I:=1 TO NUMTRIALS DO
	BEGIN
	PLAYER:=1;
	CHANGE:=1;
	DIE:=0;
	COUNTER:=0;
	WHILE DIE <> 6 DO
	     BEGIN
	     RANDOMM(X);
	     DIE:=X DIV C + 1;
	     COUNTER:= COUNTER + 1;
	     IF COUNTER = CHANGE THEN
		BEGIN
		COUNTER:=0;
		CHANGE:=CHANGE + 1;
		PLAYER:=3 - PLAYER;
		END
	     END;
	IF PLAYER =1 THEN WINS:= WINS + 1
	END;
	WRITELN(`PLAYER 1 WINS', WINS, `OUT OF', NUMTRIALS);
	WRITELN(`FOR AN ESTIMATED PROBABILITY', WINS/NUMTRIALS);
	WRITELN(`SEED WAS', SEED)

Exercise:

Simulate an island populated by wolves and rabbits.  The island is square,
and looks very much like a 50-by-50 array of regions.  Each region of the
island may be empty, or contain a wolf or a rabbit.  At each day, each wolf
has a 25% probability of moving to any adjacent wolf-free region, eating
any rabbit found there.  Rabbits have a 25% probability of moving to any
adjacent empty region.  Rabbits have a 5% probability per day of
reproducing ****fill in****.  A wolf starves if it has not eaten a rabbit
for     days.  Wolves have a       probability per day of reproducing.

Simulate the population of the island for 1000 days, printing a map showing
locations of the animals every 200th day, and tabulating the populations at
10 day intervals.  Initially, place about 10 wolves and 500 rabbits at
random.